package com.zboin.interview150.dynamic;

import java.util.List;

/** Normal
 *给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
 * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
 *
 * 示例 1：
 * 输入: s = "leetcode", wordDict = ["leet", "code"]
 * 输出: true
 * 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
 *
 * 示例 2：
 * 输入: s = "applepenapple", wordDict = ["apple", "pen"]
 * 输出: true
 * 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
 *      注意，你可以重复使用字典中的单词。
 *
 * 示例 3：
 * 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
 * 输出: false
 *
 * 提示：
 * 1 <= s.length <= 300
 * 1 <= wordDict.length <= 1000
 * 1 <= wordDict[i].length <= 20
 * s 和 wordDict[i] 仅由小写英文字母组成
 * wordDict 中的所有字符串 互不相同
 */
public class Course139 {

    public static void main(String[] args) {
        List<Result> list = List.of(
                new Result("leetcode", List.of("leet", "code"), true),
                new Result("applepenapple", List.of("apple", "pen"), true),
                new Result("catsandog", List.of("cats", "dog", "sand", "and", "cat"), false),
                new Result("cars", List.of("car","ca","rs"), true)
        );

        Course139 course139 = new Course139();

        list.forEach(item -> {
            boolean result = course139.wordBreak(item.s, item.wordDict);
            System.out.println("result = " + result + " " + (result == item.expected ? "√" : "X"));
        });

    }

    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < wordDict.size(); i++) {
            max = Math.max(max, wordDict.get(i).length());
        }
        for (int i = 1; i <= len; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (i - j > max) break;
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[len];
    }

    /**
     * 官方题解
     */
    public boolean wordBreak_main(String s, List<String> wordDict) {
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        // dp[i] 代表 i 之前位置的字符串可以由字典组成，因此 dp[0] = true
        // 对于当前位置在 i 时 s[0-i] 的字符串如果合法，那么一定存在一点 j, s[j-i] 属于字典，s[o-j]合法
        // 这里用 db[j] 来记录 db[0-j] 是否合法
        dp[0] = true;
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[len];
    }

    private static class Result {
        String s;
        List<String> wordDict;
        boolean expected;

        public Result(String s, List<String> wordDict, boolean expected) {
            this.s = s;
            this.wordDict = wordDict;
            this.expected = expected;
        }
    }
}
